<!DOCTYPE html>
<html>
    <head>
        <meta charset='utf-8'>
        <meta name="viewport" content="width=device-width,initial-scale=1.0">
        <meta http-equiv="X-UA-Compatible" content="IE=edit,chrome=1">
        <title>亲自试验自己算法的时间复杂度</title>
    </head>
    <body>
        <pre  class="language-JavaScript">
            <code>
                // O(logN)
            function binarySearch(arr, n, target) {
                let l = 0, r = n - 1;
                while(l <= r) {
                    let mid = (l + (r - l) / 2) >> 0;
                    if(arr[mid] === target) return mid;
                    if(arr[mid] > target) r = mid - 1;
                    else l = mid + 1;
                }
                return -1;
            }

            // O(N)
            function findMax(arr, n) {
                if(n <= 0) return ;

                let res = arr[0];
                for(let i = 1; i < n; i ++) {
                    if(arr[i] > res)
                        res = arr[i];
                }
                return res;
            }

            //O(NlogN) 归并排序
            function _merge(arr, l, mid, r, aux) {
                let i = l, j = mid + 1;
                for(let k = l; k <= r; k ++) {
                    if(i > mid) {
                        arr[k] = aux[j]; 
                        j ++;
                    } else if(j > r) {
                        arr[k] = aux[i];
                        i ++;
                    } else if(aux[i] < aux[j]) {
                        arr[k] = aux[i]; 
                        i++;
                    } else {
                        arr[k] = aux[j];
                        j ++;
                    }
                }
            }

            function mergeSort(arr, n) {
                let aux = new Array(n);
                for(let i = 0; i < n; i ++) {
                    aux[i] = arr[i];
                }
                for(let sz = 1; sz < n; sz += sz) {
                    for(let i = 0; i < n; i += sz + sz) {
                        _merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1), aux)
                    }
                }
            }

            // O(n^2)
            function selectionSort(arr, n) {
                for(let i = 0; i < n; i ++) {
                    let minIndex = i;
                    for(let j = i + 1; j < n; j ++) {
                        if(arr[j] < arr[minIndex]) {
                            minIndex = j;
                        }
                    }
                    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
                }
            }
            </code>
        </pre>
        <script>
            // O(logN)
            function binarySearch(arr, n, target) {
                let l = 0, r = n - 1;
                while(l <= r) {
                    let mid = (l + (r - l) / 2) >> 0;
                    if(arr[mid] === target) return mid;
                    if(arr[mid] > target) r = mid - 1;
                    else l = mid + 1;
                }
                return -1;
            }

            // O(N)
            function findMax(arr, n) {
                if(n <= 0) return ;

                let res = arr[0];
                for(let i = 1; i < n; i ++) {
                    if(arr[i] > res)
                        res = arr[i];
                }
                return res;
            }

            //O(NlogN) 归并排序
            function _merge(arr, l, mid, r, aux) {
                let i = l, j = mid + 1;
                for(let k = l; k <= r; k ++) {
                    if(i > mid) {
                        arr[k] = aux[j]; 
                        j ++;
                    } else if(j > r) {
                        arr[k] = aux[i];
                        i ++;
                    } else if(aux[i] < aux[j]) {
                        arr[k] = aux[i]; 
                        i++;
                    } else {
                        arr[k] = aux[j];
                        j ++;
                    }
                }
            }

            function mergeSort(arr, n) {
                let aux = new Array(n);
                for(let i = 0; i < n; i ++) {
                    aux[i] = arr[i];
                }
                for(let sz = 1; sz < n; sz += sz) {
                    for(let i = 0; i < n; i += sz + sz) {
                        _merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1), aux)
                    }
                }
            }

            // O(n^2)
            function selectionSort(arr, n) {
                for(let i = 0; i < n; i ++) {
                    let minIndex = i;
                    for(let j = i + 1; j < n; j ++) {
                        if(arr[j] < arr[minIndex]) {
                            minIndex = j;
                        }
                    }
                    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
                }
            }
        </script>
    </body>
</html>